1. Field of the Invention
This invention relates to image and video processing, and in particular, it relates to a device and method for entropy encoding/decoding with encryption/decryption.
2. Description of the Related Art
Conventional entropy coding methods and hardware for image and video compression use pre-defined tables to map symbol to codewords. Integrated multimedia compression and encryption systems using modified entropy coders with multiple statistical models have been proposed.
One reference, “Design of Integrated Multimedia Compression and Encryption Systems”, Chung-Ping Wu and C.-C. Jay Kuo, IEEE TRANSACTIONS ON MULTIMEDIA, Vol. 7, No. 5, October 2005 (the “Wu and Kuo article”), describes two encryption schemes which apply a multiple statistical models approach to a Huffman coder and a QM coder (QM is a simplified case of an adaptive arithmetic coder) in encoding audio/video/image data such as MPEG audio, MPEG video, and JPEG/JPEG2000 images. In this article, the modified Huffman coding scheme is referred to as a multiple Huffman table (MHT) coding scheme and the modified QM coding scheme is referred to as the multiple state indices (MSI) coding scheme.
Another reference, “Multimedia Encryption with Joint Randomized Entropy Coding and Rotation in Partitioned Bitstream”, Dahua Xie and C.-C. Jay Kuo, Hindawi Publishing Corporation, EURASIP Journal on Information Security, Volume 2007 (the “Xie and Kuo article”), describes an encryption approach that consists of two cascaded modules, the first being randomized entropy coding (REC) which uses multiple entropy coding parameters/settings according to a random sequence inside the entropy coder, the second being rotation in partitioned bitstream (RPB) which further performs a random rotation to the output of the REC stage to yield the final bitstream. Two REC schemes were described; one is referred to as randomized Huffman table (RHT) scheme for Huffman coding, the other one is referred to as randomized arithmetic coding convention interleaving (RACCI) scheme for arithmetic coding.
The RHT is an expansion of the MHT approach previously described by Wu and Kuo. In the RHT encryption scheme, a number of different Huffman codes that correspond to the same Huffman tree are constructed and published. The different Huffman codes can be constructed using a technique called the Huffman tree mutation process. Then, a particular Huffman code is chosen to encode each input symbol according to a key hopping sequence (KHS). The KHS is a sequence of numbers generated from a secret seed (key) s by a pseudorandom bit generator (PRBG). To decode the encoded bitstream, the key (random seeds) must be known in order to reproduce the KHS using the PRBG and in turn correctly decode the Huffman codewords in the bitstream.
The RHT algorithm is illustrated by an example shown in FIG. 1A, which is adapted from the Xie and Kuo article. The source input is composed of seven symbols, denoted A through G. Two different Huffman codes (Huffman trees), code #0 101 and code #1 102, are constructed to encode these seven symbols. The topologies of these two Huffman trees are the same (i.e. the two Huffman codes are isomorphic codes of each other) so the codeword length for each symbol is identical, although the codeword values are different. In this example, the 0 and 1 pairs are swapped at four places as indicated by underlines in code #1 in FIG. 1A. A sample input plaintext 103 “ACDABEFG” is encoded using a KHS 105 “10011010”. A “0” in the KHS indicates that Huffman code #0 is used to encode the corresponding plaintext symbol while “1” indicates the use of Huffman code #1. The resulting ciphertext (encoded bitstream) 107 is “110111001001110101011111” (here, the short vertical lines denote the boundaries of Huffman codewords). As a comparison, FIG. 1A also shows another KHS 104 “00000000”, with a resulting ciphertext 106 “010111000100110111101111” (the short vertical lines again denote the boundaries of Huffman codewords). The all-zero KHS 104 is equivalent to the conventional Huffman coding scheme using only one Huffman code (code #0). The bits indicated by underlines in the ciphertext 107 show where the ciphertext 107 differs from the ciphertext 106.
If the ciphertext 107 (encoded using the KHS 105) is decoded using an incorrect KHS, the resulting decoded plaintext will not be the same as the input plaintext 103. For example, if a KHS “00000000” is used to decode it, the resulting plaintext would be “EDBFCAG”; if a KHS “10111010” is used, the resulting plaintext would be “ACAABAEA”. As noted in the Xie and Kuo article, since Huffman code is a uniquely decodable code, decoding can always continue with any KHS; this decoding error will not be detected until the wrong results are further converted to raw multimedia content and found meaningless.
In the RHT algorithm described in the Xie and Kuo article, more generally, M=2m Huffman tables are generated and numbered from 0 to M−1. The KHS is broken into m-bit blocks, each value ti of a m-bit block represents a number from 0 to M−1, and the Huffman table ti is used to encode the i-th symbol.
The RACCI scheme descried in the Xie and Kuo article similarly use a randomization technique in the coding. Simply stated, arithmetic coding involves recursive interval subdivision, i.e. a process of repeatedly dividing a probability interval, and a bitstream representing the current intervals at the points of the division is generated. In binary arithmetic coding, there are two possible symbol orderings, i.e., the LPS (less probable symbol) subinterval above the MPS (more probable symbol) subinterval, or the MPS subinterval above the LPS subinterval; there are also two possible code stream conventions, i.e., points to the bottom or the top of an interval. These lead to a total of four possible coding conventions, which are indicated by an arithmetic indicator. The four coding conventions are illustrated in FIG. 1B, which is adopted from FIG. 3 of the Xie and Kuo article. Under the RACCI scheme, the coding conventions used to code each input is selected based on a KHS. Again, the KHS is generated from a secrete seed (key) s by a PRBG.
The MHT described in the Wu and Kuo article and the RHT scheme described in the Xie and Kuo article share a basic theme of employing multiple Huffman tables for coding a plaintext. For convenience, this disclosure uses the term “randomized Huffman coding” to refer to both MHT and RHT. Similarly, this disclosure uses the term “randomized arithmetic coding” to refer to both the MSI scheme described in the Wu and Kuo article and the RACCI scheme described in the Xie and Kuo article.